Secret-sharing is a tool used in many cryptographic protocols. Secret-sharing schemes have numerous applications in cryptography and distributed computing including secure information storage, secure multiparty computations, access control and more. A secret-sharing scheme involves a dealer who has a secret, a set of n parties, and a collection of subsets of k parties. According to a secret-sharing scheme, the dealer distributes shares to the parties such that any subset of k parties can reconstruct the secret from its shares, and any subset with less than k parties cannot reveal any partial information on the secret.
PCT/IL2015/050528 discloses a method for establishing a secure interconnection between a source and a destination over a public infrastructure using secret sharing (such as the secret sharing method described in “How to Share a Secret”, A. Shamir, Communications of the ACM, No. 11, Vol. 22, or equivalent methods). According to this method a plurality of intermediating nodes are deployed in different locations over the network, to create a plurality of fully or partially independent paths in different directions on the path from the source to the destination, and with sufficient data separation. Then, the shares are sent over the plurality of fully or partially independent paths while forcing shares' carrying packets to pass through selected intermediate nodes, such that no router at any intermediating nodes intercepts sufficient shares to reveal the secret. The basic assumption is that there is no sniffing of data on all communication paths at the same time, and therefore, data transmission over the separated paths secure.
However, there are situations when such a separation cannot be guaranteed and the secret shares may pass via a single country or location, such that sniffing all the transmitted shares is possible. For example, even though backup paths (communication lines) are used for keeping such a separation, there are time periods when some backup paths will be down for maintenance purposes. As a result, these time periods will be “vulnerability time windows”, during which the data transfer will not be secure.
One way of obtaining secure data transfer without using cryptographic keys (signed by a trusted Certification Authority) is to use secret shares in a form of points on randomly defined polynomial with a (free) coefficient being the secret. In this case, the source randomly selects bits that are actually transmitted, which correspond to values (x,y) on a polynomial which is unknown to the destination. The destination, which receives the transmitted values (x,y), can use extrapolation to reconstruct the polynomial that is selected by the source which defines the values (x,y), and find the secret (typically represented by the free coefficient of the polynomial) and additional genuine random bits used by the source to define the other coefficient(s) of the polynomial.
Another aspect to be solved for using secret sharing for communication between parties is authentication, since the identity of the destination which is authenticated at a particular transmission time, e.g., by coupling the party with IP/MAC address or other identity, at some (starting) point may not be valid afterwards, and if not valid in any point including the very first point of the communication (due to for example, IP spoofing) then communication should stop and cannot be understood by any other entity.
An additional problem relates to the integrity of the transmitted data, since a sniffing attacker may intercept secret shared transmission and inject/replace one or more data packets with other packets along paths from source to destination. In this case, if the attacker who changes the packets corrects its CRC according to the requirements of the transmission protocol, as well, it will be very hard to detect such corruption made to the transmitted data and therefore, as the (reconstructed from secret shares) message received at the destination may be corrupted in an undetectable way.
It is therefore an object of the present invention, to provide schemes for accumulating an OTP by the sender and the receiver using genuine randomization produced by the parties and the random polynomial used for secret sharing and/or genuine random bits sent as part of message padding.
It is another object of the present invention, to provide a method and system for keeping continuous secure communication between parties that is based on secret sharing, even if all secret shares are collected in one or more points along the communication paths for a certain bounded period of time (during which communication security is vulnerable to all secret shares sniffing).
It is another object of the present invention, to provide a method and system for authenticating communication between parties that is secured by secret sharing, even during a vulnerability window when all secret shares are collected in one or more points along the communication paths.
It is a further object of the present invention, to provide a method and system for continuously detecting the integrity of data exchanged between source and destination that is based on secret sharing, even during a vulnerability window when all secret shares are collected in one or more points along the communication paths.
Other objects advantages of the present invention will become clear as the description proceeds.